// https://www.acwing.com/problem/content/851/

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 510;          // 最大的结点数目
const int MAX_P = 0x3F3F3F3F;   // 默认的最大距离，表示不可达（这是一个很大的数，约等于10^9）
int n, m;                       // n:结点数目, m:边的数目
int dist[MAX_N];                // 从起点到各个结点的当前最短距离，刚开始由用户输入，后续使用 Dijkstra 算法更新
bool visited[MAX_N];            // 标记数组，true表示该结点的最短距离已确定
int path[MAX_N][MAX_N];         // 邻接矩阵，存储结点之间的直接距离

int dijkstra() {
    // Dijkstra算法核心流程（朴素版）- 时间复杂度O(n^2)
    // 需要循环n-1次，因为除了起点外还有n-1个结点需要确定最短路径
    for (int i = 0; i < n - 1; i++) {
        int t = -1;  // t用于记录当前未访问结点中距离起点最近的结点编号

        // 第一步：在未确定最短路径的结点中，找到距离起点最近的那个结点
        for (int j = 1; j <= n; j++) {
            // 条件解释：
            // 1. !visited[j]: 结点j还未确定最短路径
            // 2. t == -1: 还没有找到候选结点
            // 3. dist[j] < dist[t]: 找到了一个更近的候选结点
            if (!visited[j] && (t == -1 || dist[j] < dist[t])) {
                t = j; // 更新当前最近结点
            }
        }

        // 第二步：用找到的最近结点t来更新其他所有结点的距离
        for (int j = 2; j <= n && t > 0; j++) {
            // 更新条件：如果通过结点t到达j比当前已知的路径更短，就更新
            // dist[t] + path[t][j] 表示：起点->t->j 的路径长度
            // dist[j] 表示：当前已知的起点->j的最短路径长度
            dist[j] = min(dist[j], dist[t] + path[t][j]);
        }

        // 第三步：标记结点t的最短路径已确定
        // 因为Dijkstra算法的贪心性质，此时dist[t]就是起点到t的真正最短距离
        visited[t] = true;
    }

    // 算法结束后检查终点n是否可达
    if (dist[n] == MAX_P) { // 如果距离仍然是初始的最大值，说明不可达
        return -1;
    }

    return dist[n]; // 返回到达终点n的最短距离
}

int main() {
    scanf("%d%d", &n, &m);

    // 1. 初始化所有距离为无穷大
    memset(dist, MAX_P, sizeof(dist));    // 所有结点初始不可达
    memset(path, MAX_P, sizeof(path));    // 所有路径初始不可达

    // 2. 设置起点到自己的距离为0
    dist[1] = 0;  // 题目中起点是1号结点

    // 3. 读取输入数据，构建邻接矩阵
    int t1, t2, d;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &t1, &t2, &d);
        // 处理重边：只保留最短的那条边
        // 因为可能存在多条连接相同结点的边，Dijkstra只需要最短的那条
        path[t1][t2] = min(path[t1][t2], d);
    }

    // 4. 执行Dijkstra算法并输出结果
    printf("%d\n", dijkstra());

    return 0;
}